package algos

// SortSelect 选择排序
func SortSelect(a []int) {
	var N = len(a)
	for i := 0; i < N; i++ {
		var min int = i
		for j := i; j < N; j++ {
			if Less(a[j], a[min]) {
				min = j
			}
		}
		Exch(a, i, min)
	}
}

// SortInsert01 插入排序：初始版
func SortInsert01(a []int) {
	var N = len(a)
	for i := 1; i < N; i++ {
		for j := i; j > 0 && Less(a[j], a[j-1]); j-- {
			Exch(a, j-1, j)
		}
	}
}

// SortInsert02 插入排序：优化版
func SortInsert02(a []int) {
	var N = len(a)
	for i := 1; i < N; i++ {
		j := i
		temp := a[j]
		for ; j > 0 && Less(temp, a[j-1]); j-- {
			a[j] = a[j-1]
		}
		a[j] = temp
		// fmt.Printf("%v", a)
		// fmt.Printf("\n")
	}
}

// SortShell 希尔排序
func SortShell(a []int) {
	var N = len(a)
	var h = 0
	for h < N/3 {
		h = h*3 + 1
	}
	for h >= 1 {
		for i := h; i < N; i++ {
			for j := i; j >= h && Less(a[j], a[j-h]); j -= h {
				Exch(a, j, j-h)
			}
		}
		h = h / 3
	}
}
func min(a, b int) int {
	if a > b {
		return b
	}
	return a

}

// SortMergeBu4 自下而上的归并排序，不复制辅助数组
func SortMergeBu4(a []int) {
	var N = len(a)
	var aux = make([]int, N)
	for i := 0; i < N; i++ {
		aux[i] = a[i]
	}
	for sz := 2; sz/2 < N; sz = sz + sz {
		for lo := 0; lo <= N-1; lo = lo + sz {
			merge4(aux, a, lo, min(lo+sz-1, N-1), lo+sz/2-1)
		}

	}
}

// SortMergeBu3 自下而上的归并排序，通过已排序的数组不合并
func SortMergeBu3(a []int) {
	var N = len(a)
	var aux = make([]int, N)
	for sz := 2; sz/2 < N; sz = sz + sz {
		for lo := 0; lo <= N-1; lo = lo + sz {
			if lo+sz/2 <= N-1 && Less(a[lo+sz/2-1], a[lo+sz/2]) {
				continue
			}
			merge(a, aux, lo, min(lo+sz-1, N-1), lo+sz/2-1)
		}
	}
}

// SortMergeBu2 自下而上的归并排序，通过小规模数组使用插入排序优化
func SortMergeBu2(a []int) {
	var N = len(a)
	var aux = make([]int, N)
	for sz := 2; sz/2 < N; sz = sz + sz {
		for lo := 0; lo <= N-1; lo = lo + sz {
			if sz <= 16 {
				SortInsert02(a[lo:min(lo+sz, N)])
				continue
			}
			merge(a, aux, lo, min(lo+sz-1, N-1), lo+sz/2-1)
		}
	}
}

// SortMergeBu 自下而上的归并排序
func SortMergeBu(a []int) {
	var N = len(a)
	var aux = make([]int, N)
	for sz := 2; sz/2 < N; sz = sz + sz {
		for lo := 0; lo <= N-1; lo = lo + sz {
			merge(a, aux, lo, min(lo+sz-1, N-1), lo+sz/2-1)
		}
	}
}

// SortMerge 归并排序
func SortMerge(a []int) {
	var N = len(a)
	var aux = make([]int, N)
	sortMerge(a, aux, 0, N-1)
}
func sortMerge(a, aux []int, lo, hi int) {
	if hi <= lo {
		return
	}
	var mid = lo + (hi-lo)/2
	sortMerge(a, aux, lo, mid)
	sortMerge(a, aux, mid+1, hi)
	// fmt.Print("lo: ", lo, ", hi: ", hi, ", mid: ", mid, "\n")
	merge(a, aux, lo, hi, mid)
}

// SortMerge5 归并排序：不复制元素到辅助助手+顺序元素不处理
func SortMerge5(a []int) {
	var N = len(a)
	var temp = make([]int, N)
	for i := 0; i < N; i++ {
		temp[i] = a[i]
	}
	sortMerge5(a, temp, 0, N-1)
}
func sortMerge5(a, temp []int, lo, hi int) {
	if hi <= lo {
		return
	}
	var mid = lo + (hi-lo)/2
	sortMerge5(temp, a, lo, mid)
	sortMerge5(temp, a, mid+1, hi)
	if Less(temp[mid], temp[mid+1]) {
		for i := lo; i <= hi; i++ {
			a[i] = temp[i]
		}
		return
	}
	merge4(temp, a, lo, hi, mid)
}

// SortMerge4 归并排序：不将元素复制到辅助数组
func SortMerge4(a []int) {
	var N = len(a)
	var aux = make([]int, N)
	for i := 0; i < N; i++ {
		aux[i] = a[i]
	}
	sortMerge4(aux, a, 0, N-1)
}
func sortMerge4(a, aux []int, lo, hi int) {
	if hi <= lo {
		return
	}
	var mid = lo + (hi-lo)/2
	sortMerge4(aux, a, lo, mid)
	sortMerge4(aux, a, mid+1, hi)
	merge4(a, aux, lo, hi, mid)
}
func merge4(a, aux []int, lo, hi, mid int) {
	// fmt.Print("lo: ", lo, " ,hi: ", hi, "\n")
	// fmt.Print("merge aux: ", aux[lo:hi+1], "\n")
	// fmt.Print("merge a: ", a[lo:hi+1], "\n")
	var i, j = lo, mid + 1
	for k := lo; k <= hi; k++ {
		if i > mid {
			aux[k] = a[j]
			j++
		} else if j > hi {
			aux[k] = a[i]
			i++
		} else if Less(a[i], a[j]) {
			aux[k] = a[i]
			i++
		} else {
			aux[k] = a[j]
			j++
		}
	}
}

// SortMerge3 归并排序：测试数组是否已经有序
func SortMerge3(a []int) {
	var N = len(a)
	var aux = make([]int, N)
	sortMerge3(a, aux, 0, N-1)
}
func sortMerge3(a, aux []int, lo, hi int) {
	if hi <= lo {
		return
	}
	var mid = lo + (hi-lo)/2
	if hi-lo < 15 {
		SortInsert02(a[lo : hi+1])
		// fmt.Printf("N<15: %v\n", a[lo:hi])
	} else {
		sortMerge3(a, aux, lo, mid)
		sortMerge3(a, aux, mid+1, hi)
		if Less(a[mid], a[mid+1]) {
			return
		}
		merge3(a, aux, lo, hi, mid)
		// fmt.Printf("N>15: %v\n", a[lo:hi])
	}
}

// SortMerge2 归并排序：小规模数组使用插入排序
func SortMerge2(a []int) {
	var N = len(a)
	var aux = make([]int, N)
	sortMerge2(a, aux, 0, N-1)
}

func sortMerge2(a, aux []int, lo, hi int) {
	if hi <= lo {
		return
	}
	var mid = lo + (hi-lo)/2
	if hi-lo < 15 {
		SortInsert02(a[lo : hi+1])
		// fmt.Printf("N<15: %v\n", a[lo:hi])
	} else {
		sortMerge2(a, aux, lo, mid)
		sortMerge2(a, aux, mid+1, hi)
		merge(a, aux, lo, hi, mid)
		// fmt.Printf("N>15: %v\n", a[lo:hi])
	}
}

func merge3(a, aux []int, lo, hi, mid int) {
	var i, j = lo, mid + 1
	for v := lo; v <= hi; v++ {
		aux[v] = a[v]
	}
	for k := lo; k <= hi; k++ {
		if i > mid {
			a[k] = aux[j]
			j++
		} else if j > hi {
			a[k] = aux[i]
			i++
		} else if Less(aux[i], aux[j]) {
			a[k] = aux[i]
			i++
		} else {
			a[k] = aux[j]
			j++
		}
	}
}

func merge(a, aux []int, lo, hi, mid int) {
	// fmt.Print("merge a: ", a[lo:hi+1], "\n")
	var i, j = lo, mid + 1
	for v := lo; v <= hi; v++ {
		aux[v] = a[v]
	}
	for k := lo; k <= hi; k++ {
		if i > mid {
			a[k] = aux[j]
			j++
		} else if j > hi {
			a[k] = aux[i]
			i++
		} else if Less(aux[i], aux[j]) {
			a[k] = aux[i]
			i++
		} else {
			a[k] = aux[j]
			j++
		}
	}
	// fmt.Print("after merge a: ", a[lo:hi+1], "\n")
}
